C Mængder, kvantorer, udsagn og beviser

En mængde $A$ er en samling af forskellige objekter. Denne noget intuitive beskrivelse af en mængde er tilstrækkelig i de fleste sammenhænge, og vi vil ikke præcisere definitionen nærmere (hvilket hurtigt bliver ret kompliceret). Et objekt $a$ i en mængde $A$ kaldes også for et element i $A$, og vi skriver i givet fald $a \in A$. I dette tilfælde siger vi også, at $a$ tilhører $A$. Hvis et givet objekt $b$ ikke tilhører $A$, så skriver vi $b \notin A$. En mængde $A$ kaldes endelig, hvis den kun indeholder endeligt mange elementer. I modsat fald kaldes $A$ for en uendelig mængde. Blandt de endelige mængder findes den tomme mængde $\emptyset$; altså mængden der ikke indeholder nogen objekter.Mængder kan beskrives ved at fortælle, hvilke objekter de indeholder. F.eks. betyder at $A$ er en mængde bestående af tallene $1$, $2$ og $5$. En notation af formen betyder, at $B$ er mængden bestående af alle heltal fra $1$ til $271$. I (C.1) præciserer vi ikke alle elementer i $B$, men angiver alene et mønster for, hvordan elementerne i $B$ fremkommer.To mængder $A$ og $B$ er identiske, hvis de indeholder de samme elementer, og vi skriver i givet fald $A=B$. Notationen $A \subseteq B$ anvendes, hvis ethvert element i $A$ også er et element i $B$; i givet fald kalder vi $A$ for en delmængde af $B$. Det er derfor klart, at $A=B$ er det samme som, at både $A \subseteq B$ og $B \subseteq A$. Mange sætninger udtaler sig om, at to givne mængder $A$ og $B$ er ens, og ofte vises sådanne udsagn ved at vise, at ethvert element i $A$ også er et element i $B$ (dvs. $A \subseteq B$) og vice versa (dvs. $B \subseteq A$).Såfremt $C$ er en mængde, og $A$ og $B$ begge er delmængder af $C$, så anvender vi notationen $A \cup B$ om foreningen af $A$ og $B$; dvs. om den delmængde af $C$, der består af de elementer, der enten tilhører $A$ eller $B$. Notationen $A \cap B$ betegner fællesmængden af $A$ og $B$, og er den delmængde af elementer i $C$, der både tilhører $A$ og $B$. Endeligt vil vi anvende notationen $A \setminus B$ om den delmængde i $C$, der består af de elementer, der tilhører $A$, men som ikke tilhører $B$. F.eks. har vi da, at hvis $C=\{ 1,2,3,4,5,6 \}$, $A=\{ 1,2,3,4 \}$ og $B=\{2,4,6 \}$ at I disse noter vil vi anvende betegnelsen $\mathbb{Z}$ om mængden af alle heltal; dvs. mens mængden af positive heltal vil blive betegnet med og vil blive omtalt som de naturlige tal. Herudover, så anvender vi notationen $\mathbb{Q}$ om mængden af rationale tal (dvs. tal på formen $\frac{p}{q}$, for $p,q \in \mathbb{Z}$). Mængden af reelle og komplekse tal vil blive betegnet med hhv. $\mathbb{R}$ og $\mathbb{C}$.

C.1 Udsagn

Et matematisk udsagn (eller blot et udsagn) er en udtalelse, der enten er sand eller falsk. F.eks. er udtalelsen “$1=2$” falsk og dermed et udsagn. Tilsvarende er udtalelsen “$2=1+1$” sand og dermed også et udsagn. Derimod er udtalelsen “21 gule biler” hverken sand eller falsk og dermed ikke et matematisk udsagn. To udsagn $p$ og $q$ siges at være ækvivalente, hvis de har samme sandhedsværdi; dvs. hvis enten $p$ og $q$ begge er sande udsagn, eller begge er falske udsagn.

Quiz

Ud fra to udsagn $p$ og $q$ kan vi konstruere andre udsagn. Vi skriver:

1. $p \wedge q$ om udsagnet der alene er sandt, hvis $p$ og $q$ begge er sande.
2. $p \vee q$ om udsagnet der alene er falsk, hvis $p$ og $q$ begge er falske.
3. $\neg p$ om udsagnet der alene er falsk, når $p$ er sandt (dvs. specielt er $\neg p$ sandt, når $p$ er falsk).
4. $p \Rightarrow q$ om udsagnet der alene er falsk, hvis $p$ er sand og $q$ er falsk.
5. $p \Leftarrow q$ om udsagnet $q \Rightarrow p$.
6. $p \Leftrightarrow q$ om udsagnet der alene er sandt, hvis $p$ og $q$ er ækvivalente udsagn.

Det er en nyttig opgave at vise, at $p \Leftrightarrow q$ er sandt, netop når både $p \Rightarrow q$ og $q \Rightarrow p$ er sande. Med andre ord er følgende udsagn sandt En sætning udtaler sig om, hvorvidt et givet udsagn er falsk eller sandt. F.eks. skal en sætning af formen forstås som, at udsagnet $p \Leftrightarrow q$ er sandt; dvs. at $p$ og $q$ er ækvivalente udsagn. Ifølge (C.2) så kan et sådant udsagn vises ved at vise følgende to udsagn:

1. Hvis $p$ er sandt, så er $q$ sandt (svarende til at udsagnet $p \Rightarrow q$ er sandt).
2. Hvis $q$ er sandt, så er $p$ sandt (svarende til at udsagnet $q \Rightarrow p$ er sandt).

Til tider vælger man at studere sandhedsværdien af udsagnet $p \Rightarrow q$ ved at studere det kontraponerede udsagn $\neg q \Rightarrow \neg p$. At dette er muligt skyldes, at $p \Rightarrow q$ og $\neg q \Rightarrow \neg p$ er ækvivalente udsagn; dvs. følgende udsagn er sandt Det overlades til læseren at indse denne ækvivalens.

Quiz

C.2 Kvantorer

I formulering af udsagn anvender vi ofte al-kvantoren $\forall$ og eksistens-kvantoren $\exists$. Disse kvantorer er matematisk notation for hhv. “for alle” og “der eksisterer”. F.eks. udtrykker udsagnet at kvadratet på alle reelle tal er positivt eller lig $0$. Kvantorer kan også kombineres som f.eks. i der udtrykker, at der for alle reelle tal $x$, eksisterer et reelt tal $y$, der er mindre end $x$. Til tider anvendes notationen $\exists !$ som betegnelse for, at “der eksisterer et entydigt”. F.eks. udtrykker at der eksisterer et entydigt naturligt tal med kvadrat 25.

Quiz

C.3 Induktionsbeviser

Lad $A$ betegne en delmængde af de naturlige tal Vi beskriver nu et kriterium, der sikrer, at $A$ er lig $\mathbb{N}$. Vi påstår, at $A$ er lig $\mathbb{N}$ blot $A$ har følgende egenskaber:

1. $1 \in A$.
2. Hvis et element $a \in \mathbb{N}$ er indeholdt i $A$, så vil $a+1$ også være indeholdt i $A$.

Ideen er, at hvis $1 \in A$ (iflg. betingelse (1.)), så vil $2 \in A$ ifølge betingelse (2.). Herefter vil $3 \in A$ ifølge betingelse (2.), og så fremdeles. Denne egenskab ved $\mathbb{N}$ ligger til grund for induktionsbeviser.I forbindelse med induktionsbeviser betragter man en samling af udsagn indekseret ved elementerne i $\mathbb{N}$; dvs. man har et udsagn $P_i$ for ethvert $i \in \mathbb{N}$. Sættes så er $A$ en delmængde af $\mathbb{N}$. At alle udsagn $P_i$, for $i \in \mathbb{N}$, er sande, er da ækvivalent med, at $A = \mathbb{N}$. Det sidste udsagn kan tjekkes via ovenstående kriterium, og vi konkluderer dermed, at $P_i$ er sandt, for alle $i \in \mathbb{N}$, såfremt:

1. $P_1$ er sandt.
2. For alle $n \in \mathbb{N}$ gælder: Hvis $P_n$ er sandt, så er $P_{n+1}$ sandt.

Udsagn (a.) omtales også som induktionsstarten, mens (b.) kaldes induktionsskridtet. Udsagnet $P_n$ kaldes induktionshypotesen. At anvende (a.) og (b.) til at vise gyldigheden af alle udsagn $P_n$, for $n \in \mathbb{N}$, omtales som, at $P_n$ er vist via matematisk induktion i $n$. Pga. beskrivelsen af (b.) så vil der oftest være en forbindelse mellem de betragtede udsagn $P_1,P_2,P_3 \ldots$.Til tider er det nyttig at anvende en anden form for induktion, der ofte omtales som stærk induktion. Her erstattes udsagnene (a.) og (b.) med:

3. $P_1$ er sandt.
4. For alle $n \in \mathbb{N}$ gælder: Hvis $P_i$ er sandt for alle $i \leq n$, så er $P_{n+1}$ sandt.

Det overlades til læseren at overveje, at hvis (c.) og (d.) er opfyldte, så er $P_i$ sandt for alle $i \in \mathbb{N}$.Udover den ovennævnte beskrivelse af matematisk induktion så eksisterer der et væld af varianter. Oftest betragter man en samling af udsagn indekseret ved en delmængde $M$ af $\mathbb{N}$ (eller $\mathbb{Z}$); dvs. man betragter udsagn $P_n$ for $n \in M$. Hvis f.eks. så kan gyldigheden af $P_n$, for alle $n \in M$, tjekkes ved følgende betingelser:

1. $P_2$ er sandt.
2. For alle $n \geq 2$ gælder: Hvis $P_n$ er sandt, så er $P_{n+1}$ sandt.

Tilsvarende hvis så er $P_n$ sandt, for alle $n \in M$, såfremt:

1. $P_2$ er sandt.
2. For alle $n \in M \setminus \left\{ 9 \right\}$ gælder: Hvis $P_n$ er sandt, så er $P_{n+1}$ sandt.